package com.wc.算法基础课.D第四讲数学知识.质数.阶乘分解;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/4/4 23:46
 * @description https://www.acwing.com/problem/content/199/
 */
public class Main {
    static int N = (int) 1e6 + 10;
    static boolean[] st = new boolean[N];
    static int[] primes = new int[N];
    static int idx;

    static void ola(int n) {
        st[0] = st[1] = true;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) primes[++idx] = i;
            for (int j = 1; primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    public static void main(String[] args) {
        ola(N - 1);
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; primes[i] <= n; i++) {
            int t = 0;
            int x = n;
            while (x > 0) {
                t += x / primes[i];
                x /= primes[i];
            }
            System.out.println(primes[i] + " " + t);
        }
    }
}
